#include <iostream>
#include <list>
#include <string>
#include <map>
#include <utility>
#include <stdlib.h>
#include "error.h"
#include "State.h"
#include "Direction.h"

enum Symbol { sb, s1 };

struct Tuple {
	State original_state;
	Symbol read;
	Symbol write;
	Direction::dir_enum direction;
	State new_state;

	Tuple(const std::string& o, const Symbol r, const Symbol w, const Direction::dir_enum d, const std::string n)
	: original_state(state_set(o)), read(r), write(w), direction(d), new_state(state_set(n))
	{ }
};

//define type for keys used to access tuples in a map
typedef std::pair<State, Symbol> Tuple_Key;

/**
 * map needs to be able to order the keys
 * order doesn't really matter - orders by state and then symbol, a==b -> false
 */
struct Tuple_Key_Compare {
	bool operator()(const Tuple_Key& a, const Tuple_Key& b) const {
		if(a.first < b.first) return true;
		if(b.first < a.first) return false;
		if(a.second < b.second) return true;
		return false;
	}
};

class Tape {
private:
	std::list<Symbol> tape;
	std::list<Symbol>::iterator rw_head;
public:
	Tape(const std::string& input_tape, const std::map<char, Symbol>& symbol_map) {
		std::map<char, Symbol>::const_iterator position;
		for(std::string::const_iterator i = input_tape.begin(); i	!= input_tape.end(); ++i) {
			position = symbol_map.find(*i); //match a character to a symbol
			if(position == symbol_map.end()) //unknown character
				error(std::string("invalid character in input tape: ") += *i);
			tape.push_back(position->second); //add symbol to tape
		}
		rw_head = tape.begin(); //initialise read-write head
	}

	void set_start_position(int offset) {
		while(offset < 0) { //move left until offset == 0
			move(Direction::L);
			++offset;
		}
		while(offset > 0) { //move right until offset == 0
			move(Direction::R);
			--offset;
		}
	}

	//read symbol from where rw_head points on tape
	Symbol read() const { return *rw_head; }

	//write symbol to where rw_head points on tape
	void write(const Symbol& s) { *rw_head = s; }

	void move(const Direction::dir_enum& d) {
		if(d == Direction::L) {
			if(rw_head == tape.begin()) { //need to add space to start of tape
				tape.push_front(sb);
			}
			--rw_head;
		}
		else if(d == Direction::R) {
			++rw_head;
			if(rw_head == tape.end()) { //need to add space to end of tape
				tape.push_back(sb);
				rw_head = --tape.end();
			}
		}
		else {
			//C - don't need to move
		}
	}
};

typedef std::map<Tuple_Key, Tuple, Tuple_Key_Compare> Instruction_Map;

void add_instruction(Instruction_Map& map, const Tuple& tuple) {
	Tuple_Key key(tuple.original_state, tuple.read);
	std::pair<Tuple_Key, Tuple> element(key, tuple);
	if(map.insert(element).second == false)
		error(std::string("tuple already exists!"));
}

int main(int argc, char *argv[]) {
	if(argc < 2)
		error(	std::string("usage: ") += std::string(argv[0]) += std::string(" initial_tape [starting_position]"));

	//mappings of symbols to corresponding chars and inverses
	std::map<char, Symbol> symbol_map;
	std::map<Symbol, char> inverse_symbol_map; //used for output at end
	symbol_map['b'] = sb;
	inverse_symbol_map[sb] = 'b';
	symbol_map['1'] = s1;
	inverse_symbol_map[s1] = '1';

	//build State set
	state_set.add_state("q0");
	state_set.add_state("q1");
	state_set.add_state("q2");

	//build map of instructions
	Instruction_Map instruction_table;
	add_instruction(instruction_table, Tuple("q1", sb, sb, Direction::C, "q0"));
	add_instruction(instruction_table, Tuple("q1", s1, sb, Direction::R, "q2"));
	add_instruction(instruction_table, Tuple("q2", sb, s1, Direction::C, "q0"));
	add_instruction(instruction_table, Tuple("q2", s1, sb, Direction::R, "q1"));

	//create tape
	Tape tape(argv[1], symbol_map);
	if(argc == 3) //initialise rw_head of tape if required
		tape.set_start_position(atoi(argv[2]));
	
	State current_state(state_set("q1")); //start in state q1
	const Tuple* instruction;
	Instruction_Map::const_iterator iter;
	while(current_state != state_set("q0"))	{ //keep going until in HALT_STATE
		iter = instruction_table.find(Tuple_Key(current_state, tape.read()));
		if(iter == instruction_table.end())
			error("can't find instruction");
		instruction = &(iter->second);
		tape.write(instruction->write);
		tape.move(instruction->direction);
		current_state = instruction->new_state;
	}

	std::cout << "last symbol: " << inverse_symbol_map[tape.read()] << std::endl;
	
	return 0;
}
